\documentclass[a4paper]{article}
\usepackage[affil-it]{authblk}
\usepackage[backend=bibtex,style=numeric]{biblatex}
\usepackage{geometry}
\geometry{margin=1.5cm}
\usepackage{amsmath}

\title{Numerical Analysis Programming Assignment Report}
\author{Liang Yue \quad Student ID: 3220100159}
\affil{Email: 3220100159@zju.edu.cn \\ Major and Class: Information and Computational Science 2201, Zhejiang University}
\date{Due Date: \today}

\begin{document}
	
	\maketitle
	
	\section*{A. Newton Interpolation}
	
	The polynomial of Newton interpolation is given by:
	\[ P_n(x) = \sum_{k=0}^{n} f[x_0, x_1, \ldots, x_k] \prod_{i=0}^{k-1} (x - x_i) \]
	
	This problem is divided into two parts. The first part involves calculating the divided differences (\texttt{double* devidedDifference(double* x, double* y, int n)}) and storing them in an array (\texttt{f[]}).
	
	\subsection{devidedDifference(double* x, double* y, int n)}
	
	\( n \) is the number of input data points, \( x \) is the array of input points, and \( y \) is the array of function values corresponding to \( x \).
	
	Using a for loop, we sequentially calculate the divided differences at each data point, where
	\[ f[x_1, x_2, \ldots, x_n] = \frac{f[x_2, \ldots, x_n] - f[x_1, \ldots, x_{n-1}]}{x_n - x_1} \]
	
	After the loop, return \( f \).
	
	The second part involves using Newton interpolation to obtain the approximating polynomial \( P_n(x) \) and predict the value at a specific point \( a \).
	
	\subsection{double Newton(double* x, double* y, int n, double a)}
	
	\( n \) is the number of input data points, \( x \) is the array of input points, \( y \) is the array of function values corresponding to \( x \), and \( a \) is the point where the value of the polynomial is required.
	
	Using the \texttt{devidedDifference()} function, we get the divided difference table for the given data and then use the formula for \( P_n(x) \) to compute the value.
	
	First, calculate
	\[ \prod_{i=0}^{k-1} (x - x_i) \]
	
	Then multiply it by the corresponding divided difference and sum up to get the final expression.
	
	\section*{B. Application of Newton Interpolation}
	
	This problem requires the application of Newton interpolation to plot interpolating polynomials of different degrees using gnuplot.
	
	\subsection{Main Function}
	
	Define an array of node numbers and specify the interval.
	
	\subsection{generateDataFiles(ns, double c, double d)}
	
	\texttt{ns} is an array of degrees (number of nodes), and \texttt{c}, \texttt{d} are the endpoints of the interval.
	
	First, calculate the corresponding \texttt{x} values and their function values for different degrees as initial data.
	
	Using the header file \texttt{Newton.hpp}, compute the interpolating values for each point with a step size of 0.1, save them to four data files, and finally use gnuplot commands to plot the graphs.
	
	It was observed that the Runge phenomenon is evident in the plots. The image corresponds to \texttt{plot1.gp}.
	
	\section*{C. Chebyshev Polynomials}
	
	\subsection{Chebyshev.hpp}
	
	First, determine the Chebyshev nodes.
	After obtaining the nodes, use the Lagrange interpolation format to calculate the value at point \( a \) and return it to the main function for plotting.
	
	\subsection{C.cpp}
	
	Similar to B, use \texttt{generateDataFiles} to obtain the original data and the interpolating polynomial values for different \( n \). Use gnuplot to plot the graphs. It was observed that the Runge phenomenon disappears, and the fitting effect is better when \( n \) is large.(plot2.gp)
	
	\section*{Hermite Interpolation}
	
	\subsection{Hermite.hpp}
	
	Implement Hermite interpolation, which is given by:
	\[ H(x) = f(x), \quad H'(x) = f'(x) \]
	\[ H(x) = \sum_{i=0}^{n} \left[ g_i(x) f(x_i) + h_i(x) f'(x_i) \right] \]
	where
	\[ g_i(x) = \left[ 1 - 2(x - x_i) \sum_{j \neq i} \frac{1}{x_i - x_j} \right] l_i^2(x), \quad h_i(x) = (x - x_i) l_i^2(x) \]
	\[ l_i(x) = \prod_{k \neq i} \frac{x - x_k}{x_i - x_k} \]
	\subsection{D.cpp}
	In the main function, initialize \( x \), \( f \), and \( f' \).
	(a): Replace \( a \) with \( t \) and use Hermite interpolation to compute.
	(b): Set the step size and sequentially compute to find the maximum value of \( f \). The result does not exceed 81, so there is no overspeeding.
	
	\subsection{Results}
	(a)\\
	The position of the car at \( t = 10 \) seconds: 742.503 feet\\
	The speed of the car at \( t = 10 \) seconds: 48.3817 ft/s\\
	(b)\\
	The car will exceed the speed limit of 55 miles per hour.\\
	
	\section*{E. Newton Interpolation with Polynomial Output}
	
	\subsection{(a)}
	Modify the Newton interpolation code to return a polynomial. In the main function, initialize \( x \), \( y1 \), and \( y2 \), and use \texttt{NewtonPolynomials} to compute the polynomials for \( y1 \) and \( y2 \) and output them.
	
	\subsection{(b)}
	Set \( a = 43 \) and compute the average weight on day 43 under both conditions. If the average weight is less than or equal to zero, death occurs.
	
	\subsection{Results}
	(a)\\
	The polynomial for Sp1:\\
	\( 1.771667 + 6.35(a - 0) + -1.8a(a - 6.) + -1.8(a)(a - 6.)(a - 10 + -0.266667(a )(a - 6.)(a - 10)(a - 13) + -0.075(a)(a - 6)(a - 10)(a - 13)(a - 17) + 0.457833(a)(a - 6)(a - 10)(a - 13)(a - 17)(a - 20) \)\\
	
	The polynomial for Sp2:\\
	\(1.671667 + 0.55(a) + -1.300000(a)(a - 6) + -1.1(a)(a - 6)(a - 10) + -0.386667(a)(a - 6)(a - 10)(a - 13) + -0.068750(a)(a - 6)(a - 10)(a - 13)(a - 17) + -0.112167(a)(a - 6)(a - 10)(a - 13)(a - 17)(a - 20) \)\\
	(b)\\
	Neither sample of larvae will die after another 15 days.
	\section*{Bezier Curve}
	
	\subsection{Bezier.cpp}
	Based on the algorithm provided in 2.74, first use the parametric method to determine \( m+1 \) control points and then calculate the tangent vector (additional definitions for factorial and point were added as needed). 
	Then, with a step size of 0.001, compute the \( x \) and \( y \) coordinates for each point and write them to the output file for plotting.
	
	\subsection{F.cpp}
	Given the control points, since the upper bound of \( x \) is \( \sqrt{3} \), use the sine function to control and obtain \( m+1 \) control points. Substitute these into the curve to compute \( y \), and loop to calculate the data for different values of \( m \).
	
	\subsection{Error}
	During the final run, the program was unable to compute the data for \( m = 40 \). As a result, it did not exit normally and failed to compute the data for \( m = 160 \), leading to the inability to plot the graph. The error reason has not been identified, and the task remains incomplete.
	
	\end{document}